package A一周刷爆LeetCode.B基础提升.D滑动窗口与单调栈结构;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 求数组中每一个位置左右两边比他大的距离最近的位置。
 */
public class Code02_MonotonousStack {

    public static void main(String[] args) {
        int[][] nearLess = getNearLess(new int[]{6, 5, 4, 8, 3, 4, 2, 1, 7});
        for (int[] less : nearLess) {
            for (int i : less) {
                System.out.print(i);
                System.out.print(" ");
            }
            System.out.println();
        }
    }

    /**
     * 无重复值
     */
    public static int[][] getNearLessNoRepeat(int[] arr) {
        if (null == arr || arr.length == 0) {
            return null;
        }
        int[][] result = new int[arr.length][2];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                Integer pop = stack.pop();
                result[pop][0] = stack.isEmpty() ? -1 : stack.peek();
                result[pop][1] = i;
            }
            stack.add(i);
        }
        while (!stack.isEmpty()) {
            Integer pop = stack.pop();
            result[pop][0] = stack.isEmpty() ? -1 : stack.peek();
            result[pop][1] = -1;
        }
        return result;
    }

    /**
     * 有重复值
     */
    public static int[][] getNearLess(int[] arr) {
        if (null == arr || arr.length == 0) {
            return null;
        }
        int[][] result = new int[arr.length][2];
        Stack<List<Integer>> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            // 栈顶元素小于当前元素，一直弹出
            while (!stack.isEmpty() && arr[stack.peek().get(0)] < arr[i]) {
                List<Integer> pop = stack.pop();
                int leftIndex = !stack.isEmpty() ? stack.peek().get(stack.peek().size() - 1) : -1;
                for (Integer integer : pop) {
                    // 后面一个就是当前元素
                    result[integer][1] = i;
                    // 前面一个取栈顶链表的最后一个
                    result[integer][0] = leftIndex;
                }
            }
            if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
                // 栈顶元素等于当前元素，当前元素追加到后面
                stack.peek().add(i);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                stack.add(list);
            }
        }
        while (!stack.isEmpty()) {
            List<Integer> list = stack.pop();
            // 前面一个取栈顶链表的最后一个
            int leftIndex = !stack.isEmpty() ? stack.peek().get(stack.peek().size() - 1) : -1;
            for (Integer integer : list) {
                result[integer][1] = -1;
                result[integer][0] = leftIndex;
            }
        }
        return result;
    }

}
